from offer.data_structure import BinaryTreeNode


class Task7:
    def __init__(self):
        self.preorder_root_index = 0

    def run(self, preorder_list, inorder_list):
        self.preorder_root_index = 0
        return self.run_inner(preorder_list, inorder_list, 0, len(inorder_list))

    def run_inner(self, preorder_list, inorder_list, inorder_start_index, inorder_end_index):
        if inorder_end_index > inorder_start_index:
            inorder_root_index = 0
            for i in range(inorder_start_index, inorder_end_index):
                if inorder_list[i] == preorder_list[self.preorder_root_index]:
                    inorder_root_index = i
                    break

            node = BinaryTreeNode(preorder_list[self.preorder_root_index])
            if inorder_root_index > inorder_start_index:
                self.preorder_root_index += 1
                node.left = self.run_inner(preorder_list, inorder_list, inorder_start_index, inorder_root_index)
            if inorder_end_index > inorder_root_index + 1:
                self.preorder_root_index += 1
                node.right = self.run_inner(preorder_list, inorder_list, inorder_root_index + 1, inorder_end_index)
            return node
        else:
            return None
